package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/8/21 11:12 上午
 * <p>
 * https://leetcode-cn.com/problems/coin-change-2/
 * <p>
 * 输入：amount = 5, coins = [1, 2, 5]
 * 输出：4
 * 解释：有四种方式可以凑成总金额：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-change-2
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Change {


    public static void main(String[] args) {

        int amount = 5;
        int[] coins = new int[]{1, 2, 5};
        Change ex = new Change();

        int ret = ex.change(amount, coins);

        System.out.println(ret);
    }


    /**
     * dp[i][j]  表示的意思是  放入i 个coin  金额总额为 j 的 有多少种解法
     *
     * amount = 5, coins = [1, 2, 5]
     * @param amount
     * @param coins
     * @return
     */
    public int change2(int amount, int[] coins) {

        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][amount];
    }


    /**
     * dp[i][j]  表示的意思是  放入i 个coin  金额总额为 j 的 有多少种解法
     *
     * amount = 5, coins = [1, 2, 5]
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {


        int n=coins.length;
        int[] dp = new int[amount + 1];

        dp[0]=1;


        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i - 1] >= 0) {
                    dp[j] = dp[j] + dp[j - coins[i - 1]];
                }
            }
        }

        return dp[amount];

    }
}
